package org.example.myleet.p954;

import java.util.*;

public class Solution {
    public boolean canReorderDoubled(int[] arr) {
        List<Integer> numbers = new ArrayList<>(arr.length);
        for (int num : arr) {
            numbers.add(num);
        }
        numbers.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Math.abs(o1) - Math.abs(o2);
            }
        });
        Map<Integer, Integer> numberCounts = new HashMap<>(200001);
        for (int num : numbers) {
            int count = numberCounts.computeIfAbsent(num, key -> 0);
            numberCounts.put(num, ++count);
        }
        for (int num : numbers) {
            if ((num & 1) == 1) {
                continue;
            }
            int target = num / 2;
            Integer count = numberCounts.get(target);
            if (null != count) {
                if (count > 1) {
                    numberCounts.put(target, --count);
                } else {
                    numberCounts.remove(target);
                }
                count = numberCounts.get(num);
                if (null != count) {
                    if (count > 1) {
                        numberCounts.put(num, --count);
                    } else {
                        numberCounts.remove(num);
                    }
                }
            }
        }
        return numberCounts.isEmpty();
    }
}
